記憶體很貴，如果一直狂寫資料都不清理，遲早會遇到 OOM 爆掉。

為了避免這慘況，Redis 有套記憶體淘汰機制（Eviction Policy）。當記憶體快滿時（專案裡我先用限制最大 Key 個數 maxKeys 來模擬），資料庫會自動踢掉一些 Key。

今天先研究最常見的 LRU (Least Recently Used，最近最少使用)，再自己寫一版淘汰策略。

LRU 淘汰演算法怎麼想

LRU 的想法很直覺：最近有人用過的資料，等等再被用到的機率通常比較高；很久沒人碰的 Key，就先拿去淘汰。

在常規的 LRU 實作中，通常需要維護一個雙向鏈結串列（Doubly Linked List）：

• 每次訪問一個 Key，將其移動到鏈結的頭部。
• 需要淘汰時，直接刪除鏈結尾部的節點。
• 查詢時使用 Map 獲取鏈結節點，達到 O(1) 的讀寫與移動複雜度。

Redis 的「近似 LRU」優化

如果要在一個擁有數百萬 Key 的資料庫中維護一個巨大的雙向鏈結串列，會帶來嚴重的缺點：

1. 額外的記憶體開銷：每個節點需要額外存儲前後指針，浪費大量記憶體。
2. 鎖競爭激烈：每次讀操作都需要移動鏈結節點，必須對鏈結加寫鎖，導致並行讀取效能下降。

所以 Redis 實際上採用的是「近似 LRU (Approximated LRU)」：

• 它不在全域維護鏈結，而是在每個 Key 的metadata中，記錄一個 「最後訪問時間戳（Last Access Time）」。
• 當需要淘汰 Key 時，Redis 會隨機抽樣 N 個 Key（預設為 5 個），然後在其中找出訪問時間戳最久遠的那個 Key 予以淘汰。
• 這樣可以省掉鏈結的記憶體開銷，也不用每次讀取都去移動鏈結節點；效果雖然不是完全精準，但通常已經夠用。

第一次看到這做法覺得滿神奇的，原來不用維護巨大的雙向鏈結，只要抽樣幾個出來比對時間戳，效能就好上不少，真的聰明。

程式碼實作：LRU 淘汰

這次我在專案裡先提供 AllKeys-LRU（針對所有 Key）與 Volatile-LRU（只針對設有過期時間的 Key）兩種策略。

1. 記錄訪問時間戳

我們在 code/db/db.go 的 getEntryWithoutLock 讀取操作中，在加鎖保護下即時更新 lastAccessTime：

func (db *DB) getEntryWithoutLock(key string) (*entry, bool) {
	// ...
	e.lastAccessTime = time.Now() // 更新最後訪問時間戳
	e.accessCount++
	return e, true
}

2. 淘汰執行邏輯

我們在 code/db/evict.go 中實作了淘汰篩選：

func (db *DB) selectKeyToEvict() string {
	var bestKey string

	switch db.evictPolicy {
	case PolicyAllKeysLRU:
		var oldest time.Time
		first := true
		for k, v := range db.data {
			// 尋找訪問時間最久遠 (時間戳最小) 的 Key
			if first || v.lastAccessTime.Before(oldest) {
				oldest = v.lastAccessTime
				bestKey = k
				first = false
			}
		}

	case PolicyVolatileLRU:
		var oldest time.Time
		first := true
		for k, v := range db.data {
			if v.expireAt.IsZero() { continue } // 排除永久儲存的 Key
			if first || v.lastAccessTime.Before(oldest) {
				oldest = v.lastAccessTime
				bestKey = k
				first = false
			}
		}
	// ...
	}
	return bestKey
}

在寫入新鍵時（例如 Set 中），如果 len(db.data) > db.maxKeys，會自動在寫鎖內部呼叫 EvictIfNeeded()，依策略選擇並刪除最久未訪問的 Key。寫這邊的時候還得注意如果全掃一遍會卡住，所以實作上有些折衷方案。

跑起來看看

我們來驗證一下主從節點的連線流程。這邊需要開兩個終端機：一個跑主節點，一個跑從節點。

# 終端機 1: 啟動主節點 (預設 port 6379)
$ go run main.go
2026/08/13 22:45:00 [INFO] Server started on :6379

# 終端機 2: 啟動從節點 (port 6380) 並執行 SLAVEOF
$ go run main.go -port 6380
$ redis-cli -p 6380
> SLAVEOF 127.0.0.1 6379
# 預期回覆：OK

此時如果回頭看終端機 1 (主節點) 的日誌，就會看到握手與 SYNC 請求：

2026/08/13 22:45:05 [INFO] 收到來自從節點 127.0.0.1:6380 的 SYNC 請求
2026/08/13 22:45:05 [INFO] RDB 快照發送完成

總結

今天把 LRU 的基本想法和 Redis 的近似 LRU 拆了一輪，也在專案裡補上 AllKeys-LRU 跟 Volatile-LRU。

明天來看另一套 LFU（最少使用頻率），看看它怎麼處理 LRU 只看最近、不看長期熱度的問題。